package com.it.data_linkedList.leetcode;

/**
 * @author: Coke
 * @DateTime: 2023/06/07/21:37
 * 合并有序链表
 **/
public class E05LeetCode21 {
    
    /**
     * 合并有序链表（方法一）
     *
     * @param n1: 有序链表 1
     * @param n2: 有序链表 2
     * @return ListNode 合并后的链表
     * @DateTime: 2023/6/7 21:51
     * @author: Coke
     */
    public static ListNode mergeList (ListNode n1, ListNode n2) {
        ListNode s = new ListNode(- 1, null);
        ListNode p = s;
        while (n1 != null && n2 != null) {
            if (n1.val < n2.val) {
                p.next = n1;
                n1 = n1.next;
            } else {
                p.next = n2;
                n2 = n2.next;
            }
            p = p.next;
        }
        if (n1 != null) {
            p.next = n1;
        } else {
            p.next = n2;
        }
        return s.next;
    }
    
    /**
     * 合并有序链表（方法二）
     *
     * @param n1: 有序链表 1
     * @param n2: 有序链表 2
     * @return ListNode合并后的链表
     * @DateTime: 2023/6/7 22:36
     * @author: Coke
     */
    public static ListNode mergeList2 (ListNode n1, ListNode n2) {
        if (n1 == null) {
            return n2;
        }
        if (n2 == null) {
            return n1;
        }
        if (n1.val < n2.val) {
            n1.next = mergeList2(n1.next, n2);
            return n1;
        } else {
            n2.next = mergeList2(n1, n2.next);
            return n2;
        }
    }
    
    public static ListNode split (ListNode[] list) {
        return toSplit(list, 0, list.length - 1);
    }
    
    
    /**
     * 合并多个有序链表
     *
     * @param list: 有序链表 数组
     * @param i:    左边界
     * @param j:    右边界
     * @return ListNode 合并后的链表
     * @DateTime: 2023/6/8 20:15
     * @author: Coke
     */
    private static ListNode toSplit (ListNode[] list, int i, int j) {
        if (i == j) {
            return list[i];
        }
        int p = (i + j) >>> 1;
        ListNode left = toSplit(list, i, p);
        ListNode right = toSplit(list, p + 1, j);
        return mergeList(left, right);
    }
}

